package com.leetcode.algs4.search;

/**
 * @author Dennis Li
 * @date 2020/6/15 14:52
 */
public class BinarySearch {

    // 二分查找
    public static <T extends Comparable> int binarySearch(T[] arr, int k) {
        int lo = 0, hi = arr.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int compare = arr[k].compareTo(arr[mid]);
            if (compare > 0) lo = mid + 1;
            else if (compare < 0) hi = mid - 1;
            else return mid;
        }
        return lo;
    }

}
